W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
A diskette was enclosed to a road map. The diskette contains the table of the shortest ways (distances) between each pair of towns on the map. All the roads are two-way. The location of towns on the map has the following interesting property: if the length of the shortest way from town to town equals the sum of the lengths of the shortest ways from to and to then town lies on (certain) shortest way from to . We say that towns and are neighbouring towns if there is no town such that the length of the shortest way from to equals the sum of the lengths of the shortest ways from to and to .
Find all the pairs of neighbouring towns.
For the table of distances:
A B C A 0 1 2 B 1 0 3 C 2 3 0
the neighbouring towns are , and , .
Write a program that:
In the first line of the standard input there is an integer , , which equals the number of towns on the map. Towns are numbered from to .
The table of distances is written in the following lines. In the -st line, , there are non-negative integers not greater than , separated by single spaces. The -th integer is the distance between towns and .
Your program should write all the pairs of the neighbouring towns (i.e. their numbers) to the standard output. There should be one pair in each line. Each pair can appear only once. The numbers in each pair should be given in increasing order. Pairs should be ordered so that if the pair precedes the pair then or ( and ).
For the input data:
3 0 1 2 1 0 3 2 3 0
the correct result is:
1 2 1 3
Task author: Piotr Chrzastowski-Wachtel.